/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/unique-paths-ii
   @Language: C++
   @Datetime: 16-02-09 05:23
   */

class Solution {
public:
	/**
	 * @param obstacleGrid: A list of lists of integers
	 * @return: An integer
	 */
	int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
		// write your code here
		int m=obstacleGrid.size();
		if(m<1) return 0;
		int n=obstacleGrid[0].size();
		vector<vector<int> > dp(m,vector<int>(n,0));
		if(obstacleGrid[0][0]==0) dp[0][0]=1;
		else return 0;
		for(int i=0; i<m; ++i){
			for(int j=0; j<n; ++j){
				if(obstacleGrid[i][j]) continue;
				if(i>0 && obstacleGrid[i-1][j]==0) dp[i][j]+=dp[i-1][j];
				if(j>0 && obstacleGrid[i][j-1]==0) dp[i][j]+=dp[i][j-1];
			}
		}
		return dp[m-1][n-1];
	}
};
